package com.lisp.algorithm.book.c13;

import java.util.LinkedList;
import java.util.Queue;

import com.lisp.algorithm.util.Assert;

public class RedBlackTree {

	public static void main(String[] args) {
		// int a[] = {13, 10, 20, 5, 25, 30, 28, 40, 29};
		
		int a[] = {9,8,10,6};
		for(int i : a) {
			System.out.println("insert " + i);
			insert(i);
			print(true, true);
		}
		
		delete(6);
		delete(8);
		
		for(int i : a) {
			Node n = search(i);
			if(n != null) {				
				System.out.println(String.format("delete n=%s, parent=%s\n", i, n.parent.key));
				delete(n);
				print(false, true);
				print(true, true);
			}
		}
		
		for(int i=0; i<10000; i++) {
			root = null;
			for(int j=0; j<50; j++) {
				int val = new java.util.Random().nextInt(50);
				insert(val);
				print(true, false);
			}
			System.out.println("OK......");
			
			for(int j=0; j<50; j++) {
				int val = new java.util.Random().nextInt(50);
				Node node = search(val);
				if(node != null) {
					System.out.println(String.format("delete n=%s, parent=%s\n", node.key, node.parent.key));
					delete(node);
					print(true, true);
				}
			}
		}
		
		
		/*
		for(int i=0; i<a.length; i++) {
			Node n = search(a[i]);
			System.out.println(String.format("key=%s, successor=%s, predecessor=%s", 
					n, successor(n), predecessor(n)));
		}
		*/
		//delete(search(29));
		inorderTraverse(root);
	}
	
	static Node root;
	
	static Node NULL = new Node(-1, null, null, null, true);

	public static void insert(int key) {
		if(root == null || root == NULL) {
			root = new Node(key, NULL, NULL, NULL, true);
		} else {
			insert(key, root);
		}
	}
	
	private static void insert(int key, Node n) {
		if(key > n.key) {
			if(n.right == NULL) {
				Node newNode = new Node(key, n, NULL, NULL, false);
				n.right = newNode;
				fixInsertWithRotate(newNode);
			} else {
				insert(key, n.right);
			}
		} else {
			if(n.left == NULL) {
				Node newNode = new Node(key, n, NULL, NULL, false);
				n.left = newNode;
				fixInsertWithRotate(newNode);
			} else {
				insert(key, n.left);
			}
		}
	}
	
	private static void fixDelete(Node n) {
		if(n == root || !n.black) {
			n.black = true;
			return;
		}
		
		Node parent = n.parent;
		if(parent.left == n) {
			Node sibling = parent.right;
			if(sibling.black) {
				if(sibling.right != NULL && !sibling.right.black) {
					Node siblingRight = sibling.right;
					leftRotate(parent);
					sibling.black = parent.black;
					parent.black = true;
					siblingRight.black = true;
				} else if(sibling.left != NULL && !sibling.left.black) {
					Node siblingLeft = sibling.left;
					rightRotate(sibling);
					siblingLeft.black = true;
					sibling.black = false;
					fixDelete(n);
				} else {
					sibling.black = false;
					fixDelete(parent);
				}
			} else {
				leftRotate(parent);
				parent.black = false;
				sibling.black = true;
				fixDelete(n);
			}
		} else {
			Node sibling = parent.left;
			if(sibling.black) {
				if(sibling.left != NULL && !sibling.left.black) {
					Node siblingLeft = sibling.left;
					rightRotate(parent);
					sibling.black = parent.black;
					parent.black = true;
					siblingLeft.black = true;
				} else if(sibling.right != NULL && !sibling.right.black) {
					Node siblingRight = sibling.right;
					leftRotate(sibling);
					sibling.black = false;
					siblingRight.black = true;
					fixDelete(n);
				} else {
					sibling.black = false;
					fixDelete(parent);
				}
			} else {
				rightRotate(parent);
				sibling.black = parent.black;
				parent.black = false;
				fixDelete(n);
			}
		}
	}
	
	@SuppressWarnings("unused")
	private static void fixInsert(Node newNode) {
		if(newNode.parent == NULL) { // root
			newNode.black = true;
			return;
		}
		
		Node parent = newNode.parent;
		if(parent.black) {
			return;
		}
		
		Node grantParent = parent.parent;
		if(grantParent.left != NULL && !grantParent.left.black 
				&& grantParent.right != NULL && !grantParent.right.black) {
			grantParent.left.black = true;
			grantParent.right.black = true;
			grantParent.black = false;
			fixInsert(grantParent);
			return;
		}
		
		Node a, b, c, x1, x2, x3, x4;
		if(grantParent.left == parent) {
			if(parent.left == newNode) {
				a = newNode;
				b = parent;
				c = grantParent;
				x1 = a.left;
				x2 = a.right;
				x3 = b.right;
				x4 = c.right;
			} else {
				a = parent;
				b = newNode;
				c = grantParent;
				x1 = parent.left;
				x2 = newNode.left;
				x3 = newNode.right;
				x4 = grantParent.right;
			}
		} else {
			if(parent.left == newNode) {
				a = grantParent;
				b = newNode;
				c = parent;
				x1 = grantParent.left;
				x2 = newNode.left;
				x3 = newNode.right;
				x4 = parent.right;
			} else {
				a = grantParent;
				b = parent;
				c = newNode;
				x1 = grantParent.left;
				x2 = parent.left;
				x3 = newNode.left;
				x4 = newNode.right;
			}
		}
		
		if(grantParent.parent != NULL) {
			b.parent = grantParent.parent;
			if(grantParent.parent.left == grantParent) {
				grantParent.parent.left = b;
			} else {
				grantParent.parent.right = b;
			}
		} else {
			b.parent = NULL;
			root = b;
		}
		
		b.black = true;
		a.black = false;
		c.black = false;
		
		b.left = a;
		b.right = c;
		a.parent = c.parent = b;
		
		a.left = x1;
		a.right = x2;
		if(x1 != NULL) {
			x1.parent = a;
		}
		if(x2 != NULL) {
			x2.parent = a;
		}
		
		c.left = x3;
		c.right = x4;
		if(x3 != NULL) {
			x3.parent = c;
		}
		if(x4 != NULL) {
			x4.parent = c;
		}
	}
	
	private static void fixInsertWithRotate(Node newNode) {
		if(newNode.parent == NULL) { // root
			newNode.black = true;
			return;
		}
		
		Node parent = newNode.parent;
		if(parent.black) {
			return;
		}
		
		Node grantParent = parent.parent;
		if(grantParent.left != NULL && !grantParent.left.black 
				&& grantParent.right != NULL && !grantParent.right.black) {
			grantParent.left.black = true;
			grantParent.right.black = true;
			grantParent.black = false;
			fixInsertWithRotate(grantParent);
			return;
		}
		
		if(grantParent.left == parent) {
			if(parent.left == newNode) {
				rightRotate(grantParent);
				parent.black = true;
				grantParent.black = false;
			} else {
				leftRotate(parent);
				
				rightRotate(grantParent);
				newNode.black = true;
				grantParent.black = false;
			}
		} else {
			if(parent.left == newNode) {
				rightRotate(parent);
				
				leftRotate(grantParent);
				newNode.black = true;
				grantParent.black = false;
			} else {
				leftRotate(grantParent);
				parent.black = true;
				grantParent.black = false;
			}
		}
	}
	
	private static void leftRotate(Node n) {
		Node a=n, b = n.right;
		Node middleLeaf = b.left;
		
		b.parent = n.parent;
		if(n.parent != NULL) {
			if(n.parent.left == n) {
				n.parent.left = b;
			} else {
				n.parent.right = b;
			}
		} else {
			root = b;
		}
		
		a.parent = b;
		b.left = a;
		
		a.right = middleLeaf;
		if(middleLeaf != NULL) {
			middleLeaf.parent = a;
		}
	}
	
	private static void rightRotate(Node n) {
		Node a = n, b = n.left;
		Node middleLeaf = b.right;
		
		b.parent = a.parent;
		if(a.parent != NULL) {
			if(a.parent.left == a) {
				a.parent.left = b;
			} else {
				a.parent.right = b;
			}
		} else {
			root = b;
		}
		
		b.right = a;
		a.parent = b;
		
		a.left = middleLeaf;
		if(middleLeaf != NULL) {
			middleLeaf.parent = a;
		}
	}
	
	public static void delete(int key) {
		Node node = search(key);
		if(node != null) {
			delete(node);
		}
	}
	
	public static void delete(Node n) {
		if(n.left == NULL) {
			transplant(n, n.right);
			if(n.black) {
				fixDelete(n.right);
			}
		} else if(n.right == NULL) {
			transplant(n, n.left);
			if(n.black) {
				fixDelete(n.left);
			}
		} else {
			Node successor = successor(n);
			
			boolean successorOriginBlack = successor.black;
			Node successorOriginRight = successor.right;
			
			if(successor.parent != n) {
				transplant(successor, successor.right);
				successor.right = n.right;
				n.right.parent = successor;
			} else {
				// 当successorOriginRight是叶子节点时，需要让其parent指向successor
				successorOriginRight.parent = successor;
			}
			
			transplant(n, successor);
			successor.left = n.left;
			n.left.parent = successor;
			
			successor.black = n.black;
			if(successorOriginBlack) {
				fixDelete(successorOriginRight);
			}
		}
	}
	
	private static void transplant(Node origin, Node newNode) {
		if(origin.parent == NULL) { // n is root
			root = newNode;
		} else if(origin.parent.left == origin) {
			origin.parent.left = newNode;
		} else {
			origin.parent.right = newNode;
		}
		newNode.parent = origin.parent;
	}
	
	public static Node predecessor(Node n) {
		if(n == NULL) {
			return null;
		}
		if(n.left != NULL) {
			return max(n.left);
		} else {
			while(n.parent != NULL && n.parent.left == n) {
				n = n.parent;
			}
			return n.parent;
		}
	}
	
	public static Node successor(Node n) {
		if(n == NULL) {
			return null;
		}
		if(n.right != NULL) {
			return min(n.right);
		} else {
			while(n.parent != NULL && n.parent.right == n) {
				n = n.parent;
			}
			return n.parent;
		}
	}
	
	public static Node max(Node n) {
		if(n == NULL) {
			return null;
		}
		while(n.right != NULL) {
			n = n.right;
		}
		return n;
	}
	
	public static Node min(Node n) {
		if(n == NULL) {
			return null;
		}
		while(n.left != NULL) {
			n = n.left;
		}
		return n;
	}
	
	public static Node search(int key) {
		Node n = root;
		while(n != NULL) {
			if(n.key == key) {
				return n;
			} else if(n.key < key) {
				n = n.right;
			} else {
				n = n.left;
			}
		}
		return null;
	}
	
	public static void inorderTraverse(Node n) {
		if(n == NULL) {
			return;
		}
		inorderTraverse(n.left);
		System.out.print(n.key + "  ");
		inorderTraverse(n.right);
	}
	
	private static void check(Node n) {
		if(n == NULL) {
			return;
		}
		
		Assert.isTrue(n.left != null);
		Assert.isTrue(n.right != null);
		
		if(n.left != NULL) {
			Assert.isTrue(n.left.parent == n);
			if(!n.left.black) {
				Assert.isTrue(n.black);
			}
		}
		
		if(n.right != NULL) {
			Assert.isTrue(n.right.parent == n);
			if(!n.right.black) {
				Assert.isTrue(n.black);
			}
		}
	}
	
	private static int treeBlackHeight = -1;
	private static void checkLeafBlackHeight(NodeWrapper nl) {
		if(nl.node == root) {
			return;
		}
		if(treeBlackHeight == -1) {
			treeBlackHeight = nl.blackHeight;
		} else {
			Assert.isTrue(treeBlackHeight == nl.blackHeight);
		}
	}
	
	private static void print(boolean check, boolean print) {
		if(print) {
			System.out.println("-------------print start----------------check=" + check);
		}
		if(root == NULL) {
			System.out.println("red black tree is empty");
			return;
		}
		
		treeBlackHeight = -1;
		
		Queue<NodeWrapper> q = new LinkedList<NodeWrapper>();
		q.add(new NodeWrapper(root, 0, 1));
		int currentLevel = 0;
		while(!q.isEmpty()) {
			NodeWrapper nl = q.remove();
			if(currentLevel < nl.level) {
				if(print) {					
					System.out.println();
				}
				currentLevel = nl.level;
			}
			Node n = nl.node;
			
			NodeWrapper leftNl = new NodeWrapper(n.left, nl.level+1, 
					n.left.black ? nl.blackHeight + 1 : nl.blackHeight);
			if(n.left != NULL) {				
				q.add(leftNl);
			} else {
				if(check) {					
					checkLeafBlackHeight(leftNl);
				}
			}
			
			NodeWrapper rightNl = new NodeWrapper(n.right, nl.level+1, n.right.black ? nl.blackHeight + 1 : nl.blackHeight);
			if(n.right != NULL) {
				q.add(rightNl);
			} else {
				if(check) {					
					checkLeafBlackHeight(rightNl);
				}
			}
			
			if(check) {				
				check(n);
			}
			
			if(print) {				
				System.out.println(String.format("key=%s, black=%s, parent=%s", 
						n.key, n.black, n.parent == null ? "-1" : n.parent.key));
			}
		}
		
		if(print) {
			System.out.println("-------------print end----------------check=" + check);
		}
	}
	
	static class NodeWrapper {
		
		private Node node;
		private int level;
		private int blackHeight;
		
		public NodeWrapper(Node node, int level, int blackHeight) {
			super();
			this.node = node;
			this.level = level;
			this.blackHeight = blackHeight;
		}
	}

	static class Node {
		private int key;
		private Node parent;
		private Node left;
		private Node right;
		private boolean black;
		
		public Node(int key, Node parent, Node left, Node right, boolean black) {
			super();
			this.key = key;
			this.parent = parent;
			this.left = left;
			this.right = right;
			this.black = black;
		}
		
		public String toString() {
			return String.format("key=%s, black=%s", key, black);
		}
	}
}
